# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head is None:
            return True
        fast = mid = head
        while fast.next and fast.next.next:
            mid = mid.next
            fast = fast.next.next

        list1 = ListNode(mid.val)
        list2 = mid
        # if even
        if fast.next:
            list2 = mid.next

        # revert list1
        pt = head
        while pt != mid:
            tmp = pt
            pt = pt.next
            tmp.next = list1.next
            list1.next = tmp

        while list1:
            if list1.val != list2.val:
                return False
            list1 = list1.next
            list2 = list2.next
        return True

if __name__ == '__main__':
    so = Solution()
    t = h = ListNode(0)
    for x in []:
        tt = ListNode(x)
        t.next = tt
        t = tt
    print so.isPalindrome(h.next)
